import java.util.*;


public class Solution2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        Arrays.sort(numbers);
        return numbers[numbers.length/2];
    }
    public int MoreThanHalfNum_Solution2 (int[] numbers) {
        // write code here
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i<numbers.length;i++) {
            if(map.containsKey(numbers[i])) {
                map.put(numbers[i],map.get(numbers[i]) + 1);
            } else {
                map.put(numbers[i],1);
            }
        }
        for(int i = 0;i<numbers.length;i++) {
            if(map.get(numbers[i]) > numbers.length/2) {
                return numbers[i];
            }
        }
        return -1;
    }

    public int MoreThanHalfNum_Solution3 (int[] numbers) {
        // write code here
        int res = numbers[0];
        int count = 0;
        for(int i = 0;i<numbers.length;i++) {

            if(numbers[i] == res) {
                count++;
            } else {
                count--;
            }
            if(count == 0) {
                res = numbers[i+1];
            }

        }
        return res;
    }
}